#define _CRT_SECURE_NO_WARNINGS
//class Solution {
//public:
//    int maximalSquare(vector<vector<char>>& matrix) {
//        int n = matrix.size();
//        int m = matrix[n - 1].size();
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
//        int ret = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (matrix[i - 1][j - 1] == '1')
//                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
//                ret = max(ret, dp[i][j]);
//            }
//        }
//        return ret * ret;
//    }
//};
//
//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> dp1(n, 0);
//        vector<int> dp2(n, 0);
//        dp1[0] = nums[0];
//        for (int i = 1; i < n; i++)
//        {
//            dp1[i] = dp2[i - 1] + nums[i];
//            dp2[i] = max(dp2[i - 1], dp1[i - 1]);
//        }
//        return max(dp1[n - 1], dp2[n - 1]);
//    }
//};
//
//class Solution {
//public:
//    int trailingZeroes(int n) {
//        int ret = 0;
//        // long long sum = 1;
//        // for(int i = 1;i<=n;i++)
//        // {
//        //     sum*=i;
//        //     while(sum%10==0)
//        //     {
//        //         ret++;
//        //         sum/=10;
//        //     }
//        // }
//        for (int i = 5; i <= n; i += 5)
//        {
//            int tmp = i;
//            while (tmp % 5 == 0)
//            {
//                ret++;
//                tmp /= 5;
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int climbStairs(int n) {
//        vector<int> dp(n, 0);
//        dp[0] = 1;
//        if (n == 1)
//            return 1;
//        if (n == 2)
//            return 2;
//        dp[1] = 2;
//        for (int i = 2; i < n; i++)
//        {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n - 1];
//    }
//};